#include <gc/gc.h>
#include "Multitree.h"
#include "Mystrcat.h"
#include <string.h>
#include <stdlib.h>
#include <assert.h>

Multitree * give_me_empty_tree(){
	Multitree * tree;
	tree = (Multitree *) GC_MALLOC(sizeof(Multitree));
	if (tree == NULL){ /*What to do? End.*/
		abort();
	}
	/*We should initialize symbol*/
	tree->symbol.name = NULL;
	tree->symbol.number = NULL;
	return tree;
}


int treecmp(const Multitree * first, const Multitree * second){
	ListOfChilds * left;
	ListOfChilds * right;
	if (first == second){
		return 0;
	}
	if (first == NULL){ /*null is smaller*/
		return -1;
	}
	if (second == NULL){
		return 1;
	}
	int tmp;
	/*If the symbols are different, then decide according to the symbols.*/ 
	if (symbolcmp(&(first->symbol), &(second->symbol))<0){
		return -1;
	}
	if (symbolcmp(&(first->symbol), &(second->symbol)) != 0){
		return 1;
	}
	left = first->childs;
	right = second->childs;
	while(1){
		if((left == NULL) && (right ==NULL)){
			return 0; /*They are same*/
		}
		if (right == NULL){
			return -1; /*Let the one with less sons be smaller*/
		}

		if (left == NULL){
			return 1;
		}

		tmp = treecmp(left->subtree, right->subtree);

		if(tmp != 0){
			return tmp;
		}

		if(left->inverted != right->inverted){
			/*inverted is "larger"*/
			return right->inverted;
		}
		left=left->next;
		right = right->next;
	}
}




Multitree * copy_tree(Multitree * tree){
	if (tree == NULL){
		return NULL;
	}
	Multitree * copy = give_me_empty_tree();
	symbolcpy(&(copy->symbol),&(tree->symbol));
	copy->childs = NULL;
	if(tree->childs == NULL){
		//it was leaf
		return copy;
	}
	//Now we copy sons, one by one.
	ListOfChilds * added; //We add after this to new tree
	ListOfChilds * pass; //Going through tree.
	pass = tree->childs;
	added = give_me_empty_child();
	added->inverted = pass->inverted;
	added->next=NULL;
	added->subtree = copy_tree(pass->subtree);
	copy->childs = added;
	pass = pass->next;
	while(pass != NULL){
		added->next = give_me_empty_child();
		added->next->inverted = pass->inverted;
		added->next->next = NULL;
		added->next->subtree = copy_tree(pass->subtree);
		added = added->next;
		pass = pass->next;
	}
	return copy;
}


void delete_list(ListOfChilds * childs){
	ListOfChilds * next = NULL;
	while(childs !=NULL){
		next = childs->next;
		GC_FREE(childs);
		childs = next;
	}
}


/*	void delete_list(ListOfChilds * childs){
	if(childs == NULL){
		return;
	}
	delete_list(childs->next);
	delete childs;
}
*/		
void delete_childs(ListOfChilds * childs){
	ListOfChilds * pass = childs;
	while(pass != NULL){
		delete_tree(pass->subtree);
		pass = pass->next;
	}
	delete_list(childs);
}


void delete_tree(Multitree * tree){
	if(tree == NULL){
		return;
	}
	ListOfChilds * child = tree->childs;
	while(child != NULL){
		delete_tree(child->subtree);
		child = child->next;
	}
	delete_list(tree->childs);
	GC_FREE(tree->symbol.name);
	GC_FREE(tree);
}


char * treetostring(Multitree * tree){
	ListOfChilds * childs = NULL;
	size_t outputsize;
	char * output = NULL;
	char * temp = NULL;
	char * now_at = NULL;
	size_t now_allocated;
	size_t now_used;
	char * op = NULL;
	char * inop = NULL;
	if (tree == NULL){
		return "Error tree.";
	}
	childs = tree->childs;
	switch(tree->symbol.type){
		case CONSTANT:
		case VARIABLE:
			outputsize = strlen(tree->symbol.name);
			output = (char *) GC_MALLOC((outputsize +1 ) * sizeof(char*));
			if(output == NULL){
				abort();
			}
			strcpy(output, tree->symbol.name);
			return output;
			break;

		case NUMBER:
			return numtostr(tree->symbol.number);
			break;

		case FUNCTION:
			temp = treetostring(tree->childs->subtree);
			output = (char *) GC_MALLOC(8*sizeof(char)+ strlen(temp));
			if(output == NULL){
				abort();
			}
			/*Why eight? Because there should not be longer function name (with space and \0) than
			 * eight chars?
			 * basically - there should be enough space.*/
			switch (tree->symbol.func){
				case COS:
					strcpy(output, "cos ");
					break;
				case SIN:
					strcpy(output, "sin ");
					break;
				case TAN:
					strcpy(output, "tan ");
					break;
				case LN:
					strcpy(output, "ln ");
					break;
				default:
					strcpy(output, "??? ");
			}
			strcat(output, temp);
			GC_FREE(temp);
			return output;
			break;
		case OPERATOR:
			now_allocated = 128;
			now_used = 0;
			output=(char *) GC_MALLOC(now_allocated * sizeof(char));
			if(output == NULL){
				abort();
			}
			strcpy(output, "(");
			now_used++;
			now_at = output + 1; /*behind '('*/
			if (childs->inverted){
				/*Tree can be multiply or plus*/
				if (tree->symbol.oper == MULTIPLY){
					now_at = mystrcat(output, "1/");
					now_used = now_used + 2;
				}else{
					now_at = mystrcat(output, "-");
					now_used = now_used + 1;
				}
			}
			/*we have 100 chars allocated and "now_used" of them are used, but without terminating 0 (and now_at points to where 0 is)*/
			temp = treetostring(childs->subtree);
			if (strlen(temp) + now_used + 1 > now_allocated){
				now_allocated = 2* now_allocated;
				output = GC_REALLOC(output, now_allocated);
				if(output == NULL){
					abort();
				}
			}
			now_at = mystrcat(now_at, temp);
			now_used = now_used + strlen(temp);
			GC_FREE(temp);

			switch(tree->symbol.oper){
				case PLUS:
					op = "+";
					inop = "-";
					break;
				case MULTIPLY:
					op = "*";
					inop = "/";
					break;
				case POWER:
					op = "^";
					inop = "?";
					break;
			}
			childs = childs->next;
			while (childs != NULL){
				temp = treetostring(childs->subtree);
				if(strlen(temp) + 1 + now_used + 1 > now_allocated){
					/*if there is not enough space for what is already there and for operator and for new child and for \0*/
					now_allocated = 2* now_allocated;
					output = GC_REALLOC(output, now_allocated);
					if(output == NULL){
						abort();
					}
				}
					
				if (childs->inverted){
					now_at = mystrcat(output, inop);
				}else{
					now_at = strcat(output, op);
				}
				now_used = now_used + 1;
				now_at = mystrcat(now_at, temp);
				now_used = now_used + strlen(temp);
				assert(now_used = now_at - output +1);
				GC_FREE(temp);
				childs=childs->next;
			}
			if(now_allocated <= now_used + 2){
				now_allocated = 2* now_allocated;
				output = GC_REALLOC(output, now_allocated);
				if(output == NULL){
					abort();
				}
			}
			now_at = mystrcat(now_at, ")");
			assert(*now_at == '\0');
			return output;
			break;
		default:
			output = GC_MALLOC(sizeof(char) * 3);
			if(output == NULL){
				abort();
			}
			strcpy(output, "??");
			return output;
	}
}

void invert_childs(ListOfChilds * childs){
	while(childs != NULL){
		childs->inverted = !(childs->inverted);
		childs = childs->next;
	}
}

void rehang_tree(Multitree * tree){
	/*Rehang all sons and then rehang this tree, if applicable (+ or *)
	Can we do it in place? Yes. And we never change tree pointer (that is passed by value).*/
	ListOfChilds * compatible = NULL;
	ListOfChilds * others = NULL;
	ListOfChilds * following = NULL;
	ListOfChilds * pass = NULL;
	ListOfChilds * end = NULL;
	if (tree == NULL){
		return;
	}
	switch(tree->symbol.type){
		case NUMBER:
		case CONSTANT:
		case VARIABLE:
			/*We have nothing to do. There are no subtrees.*/
			return;
		case FUNCTION:
			/*Just rehang argument.*/
			rehang_tree(tree->childs->subtree);
			return;
		case OPERATOR:
			/*First, rehang all sons.*/
			pass = tree->childs;
			while (pass != NULL){
				rehang_tree(pass->subtree);
				pass = pass->next;
			}
			if(tree->symbol.oper == POWER){ /*We do not rehang anything else.*/
				return;
			}
			/*Now we divide list of sons to compatible and others.
			We completely disintegrate list of childs!*/
			pass = tree->childs;
			while (pass != NULL){
				following = pass->next;
				if (symbolcmp(&(pass->subtree->symbol), &(tree->symbol)) == 0){
					pass->next = compatible;
					compatible = pass;
				}else{
					pass->next = others;
					others = pass;
				}
				pass = following;
			}
			/*childs are divided to two strings.*/
			tree->childs = others; /*Others can be immediately added to tree;
			Now we pass through compatible and add their subtrees to tree->child.*/
			
			end = tree->childs;
			if (end == NULL){ /*No incompatible childs.
				Take first compatible and attach it's childs to tree.*/
				tree->childs = compatible->subtree->childs;
				if(compatible->inverted){ //invert, if necessary
					invert_childs(tree->childs);
				}
				following = compatible->next;
				GC_FREE(compatible->subtree);
				GC_FREE(compatible);
				compatible = following;
				end = tree->childs;
			}

			while (end->next != NULL){
				end = end->next;
			}

			pass = compatible;

			while(pass != NULL){
				following = pass->next;
				if(pass->inverted){
					invert_childs(pass->subtree->childs);
				}
				/*Now just insert pass->subtree->childs to tree->childs. (how?)*/
				end->next = pass->subtree->childs;
				while (end->next != NULL){
					end = end->next;
				}
				GC_FREE(pass->subtree);
				GC_FREE(pass);
				pass = following;
			}/*Should be all.*/
			return;
	}
}

void sort_tree(Multitree * tree){
	ListOfChilds * pass = NULL;
	ListOfChilds * from = NULL;
	Multitree * tmp = NULL;
	ListOfChilds * min = NULL;
	int cmp;
	int inv;
	if (tree == NULL){
		return;
	}
	switch (tree->symbol.type){
		case CONSTANT:
		case NUMBER:
		case VARIABLE:
			return;
			break;
		case FUNCTION:
			sort_tree(tree->childs->subtree);
			return;
			break;
		case OPERATOR:
			pass = tree->childs;
			while (pass != NULL){
				sort_tree(pass->subtree);
				pass = pass->next;
			}
			if (tree->symbol.oper == POWER){
				return;
				break;
			}
			/*Let's sort.*/
			from = tree->childs;
			while (from != NULL){
				pass = from->next;
				min = from;
				while (pass != NULL){
					cmp = treecmp(pass->subtree, min->subtree);
					if((cmp == 0)&& (min->inverted != pass->inverted)){//same trees but not same inverted.
						cmp = pass->inverted == 0?-1:1; //if pass is not inverted, it is smaller.
					}
					if (cmp < 0){
						min = pass;
					}
					pass = pass->next;
				}
				if(min != from){
					/*exchange their content*/
					tmp = from->subtree;
					inv = from->inverted;
					from->subtree = min->subtree;
					from->inverted = min->inverted;
					min->inverted = inv;
					min->subtree = tmp;
					tmp = NULL;
				}
				from = from->next;
			}
	}
}

Multitree * replace_variable_tree(Multitree * original, const char * variable, Multitree * with){
	Multitree * to_return;
	ListOfChilds * added;
	ListOfChilds * pass;
	if(original == NULL){
		return NULL;
	}

	if(with == NULL){
		return NULL;
	}

	/*Replaces variable in the original tree with "with" tree.*/
	if ((original->symbol.type == VARIABLE) && (strcmp(original->symbol.name, variable) == 0)){
			return copy_tree(with);
	}else{
		/*very similar to copy_tree
		in fact, it is copied from copy_tree.*/
		to_return  = give_me_empty_tree();
		symbolcpy(&(to_return->symbol),&(original->symbol));
		to_return->childs = NULL;
		if(original->childs == NULL){
			return to_return;
		}

		pass = original->childs;
		added = give_me_empty_child();
		added->inverted = pass->inverted;
		added->next=NULL;
		added->subtree = replace_variable_tree(pass->subtree, variable, with);
		if (added->subtree == NULL){
			return NULL;
		}
		to_return->childs = added;
		pass = pass->next;
		while(pass != NULL){
			added->next = give_me_empty_child();
			added->next->inverted = pass->inverted;
			added->next->next = NULL;
			added->next->subtree = replace_variable_tree(pass->subtree, variable, with);
			added = added->next;
			pass = pass->next;
		}
		return to_return;
	}
}

ListOfChilds * give_me_empty_child(){
	ListOfChilds * to_return;
	to_return = (ListOfChilds *) GC_MALLOC(sizeof(ListOfChilds));
	if(to_return == NULL){
		abort();
	}
	return to_return;
}

Multitree * give_me_tree_with_two_childs(){
	Multitree * tree = give_me_empty_tree();
	tree->symbol.type = OPERATOR; //only operator has more than one child.
	tree->symbol.oper = PLUS;	//plus can hold anything (no fear of zeros)
	tree->childs = give_me_empty_child();
	tree->childs->next = give_me_empty_child();
	tree->childs->next->next = NULL;
	tree->childs->next->inverted = 0;
	tree->childs->next->subtree = give_me_empty_tree();
	tree->childs->next->subtree->symbol.type = NUMBER; //make it something without childs - this can be changed later, if necessary
	//However there can be a problem - these subtrees need to be deleted when creating new tree!
	tree->childs->next->subtree->childs = NULL;
	tree->childs->inverted = 0;
	tree->childs->subtree = give_me_empty_tree();
	tree->childs->subtree->symbol.type = NUMBER;
	tree->childs->subtree->childs = NULL;
	return tree;
}

Multitree * give_me_tree_with_two_incomplete_childs(){
	Multitree * tree = give_me_empty_tree();
	tree->symbol.type = OPERATOR; //only operator has more than one child.
	tree->symbol.oper = PLUS;	//plus can hold anything (no fear of zeros)
	tree->childs = give_me_empty_child();
	tree->childs->next = give_me_empty_child();
	tree->childs->next->next = NULL;
	tree->childs->subtree = NULL;
	tree->childs->next->subtree = NULL;
	return tree;
}

Multitree * treefromnum(Number * number){
	Multitree * to_return = NULL;
	if (number == NULL){
		return NULL;
	}
	to_return = give_me_empty_tree();
	to_return->childs = NULL;
	to_return->symbol.type = NUMBER;
	to_return->symbol.number = construct_number();
	numbercpy(to_return->symbol.number, number);
	return to_return;
}

